package com.li.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test9 {


    /**
     * 基本方法：字符串匹配
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        //确定p串的长度
        int pLength = p.length();

        //分解p串
        char[] pChars = p.toCharArray();
        Arrays.sort(pChars);

        //在s中一次遍历p串长度, i=起点，j=终点
        int i = 0, j = i+pLength-1;
        while (j < s.length()) {
            //获取s子串 i~j
            String sub = s.substring(i, j+1);
            char[] subChars = sub.toCharArray();
            Arrays.sort(subChars);
            //匹配成功
            if (Arrays.compare(pChars, subChars) == 0) {
                result.add(i);
            }
            i++;
            j++;
        }
        return result;
    }

    /**
     * 字母异位子串：可以使用字母数统计 + 滑动窗口
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> result = new ArrayList<>();
        //TODO:提前计算
        if (s.length() < p.length()) {
            return result;
        }
        //统计每种字母的个数
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        int[] sLetter = new int[26];
        int[] pLetter = new int[26];
        for (int i = 0; i < pChars.length; i++) {
            sLetter[sChars[i] - 'a']++;
            pLetter[pChars[i] - 'a']++;
        }
        //TODO:判断第一个字串是否符合条件
        if (Arrays.equals(sLetter, pLetter)) {
            result.add(0);
        }
        //TODO:按区间比较字母统计数
        for (int i = 1; i <= s.length() - p.length(); i++) {
            //TODO:减去前一个字母
            sLetter[sChars[i-1] - 'a']--;
            //TODO:加上后一个字母
            sLetter[sChars[i+p.length()-1] - 'a']++;
            if (Arrays.equals(sLetter, pLetter)) {
                result.add(i);
            }
        }
        return result;
    }


    /**
     * 优化了上一方法中循环当中的数组比较：Arrays.equals(sLetter, pLetter)
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams2(String s, String p) {
        ArrayList<Integer> result = new ArrayList<>();
        if (p.length() > s.length()) {
            return result;
        }
        //TODO:统计窗口长度下，每种字母的平衡情况（p+, s-）
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        int[] count = new int[26];
        for (int i = 0; i < p.length(); i++) {
            count[pChars[i] - 'a']++;
            count[sChars[i] - 'a']--;
        }
        //TODO:遍历26个字母，统计当前差异情况
        int diff = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) {
                diff++;
            }
        }
        if (diff == 0) {
            result.add(0);
        }
        //TODO:滑动窗口，更新diff
        for (int i = 1; i <= s.length() - p.length(); i++) {
            if (count[sChars[i - 1] - 'a'] == 0) {
                diff++;
            }
            if (count[sChars[i - 1] - 'a'] == -1) {
                diff--;
            }
            count[sChars[i - 1] - 'a']++;
            if (count[sChars[i + p.length() - 1] - 'a'] == 0) {
                diff++;
            }
            if (count[sChars[i + p.length() - 1] - 'a'] == 1) {
                diff--;
            }
            count[sChars[i + p.length() - 1] - 'a']--;
            if (diff == 0) {
                result.add(i);
            }
        }
        return result;
    }




    public static void main(String[] args) {
        Test9 test9 = new Test9();
        System.out.println(test9.findAnagrams2("cbaebabacd", "abc"));
    }
}
